package ink.xiaobaibai.units;

import lombok.extern.slf4j.Slf4j;
import org.springframework.util.AntPathMatcher;

import java.util.*;

/**
 * @description: 前缀树
 * @author: 小白白
 * @create: 2021-05-25
 **/

@Slf4j
public class UriTrie {

    /**
     * 此字典树 k: char  value: string value不为空则代表是一个资源
     * uri字符只包括: 26个字母+ / + *  总共28个字符
     */

    private class UriNode {
        public UriNode(char c, String value, boolean isUri) {
            this.c = c;
            this.value = value;
            this.isUri = isUri;
        }

        public char c;
        public String value;
        public Map<Character, UriNode> nodes = new HashMap<>();
        public boolean isUri;
        public int count;
        public Set<UriNode> childUriNodeSet;

        @Override
        public int hashCode() {
            return this.value.hashCode();
        }

        @Override
        public boolean equals(Object obj) {
            return this.value.equals(((UriNode) obj).value);
        }
    }

    private AntPathMatcher antPathMatcher = new AntPathMatcher();
    private UriNode root;

    public UriTrie(List<String> uris) {
        this.root = new UriNode('@', null, false);
        this.init(uris);
    }

    private void init(List<String> uris) {
        //*节点Node
        Set<UriNode> uriNodeSet = new HashSet<>();
        for (String uri : uris) {
            if (uri == null) {
                continue;
            }
            this.add(uri, uriNodeSet);
        }
        /**
         * 开始处理*节点Node
         */
        for (UriNode uriNode : uriNodeSet) {
            this.asteriskNodeHandler(uriNode);
        }
    }

    /**
     * 加入数据库原始资源
     */
    private void add(String uri, Set<UriNode> uriNodeSet) {
        char[] chars = uri.toCharArray();
        UriNode cur = this.root;
        StringBuilder sb = new StringBuilder();
        for (char c : chars) {
            sb.append(c);
            UriNode nodes = cur.nodes.get(c);
            if (nodes == null) {
                cur.nodes.put(c, nodes = new UriNode(c, sb.toString(), false));
                cur.count++;
            }
            if (c == '*') {
                //是* 放入带有*的节点
                uriNodeSet.add(nodes);
            }
            cur = nodes;
        }
        //出来即使终点
        cur.isUri = true;
    }

    private void asteriskNodeHandler(UriNode uriNode) {
        uriNode.childUriNodeSet = new HashSet<>();
        this.dfs(uriNode, uriNode.childUriNodeSet);
    }

    private void dfs(UriNode uriNode, Set<UriNode> set) {
        if (uriNode == null) {
            return;
        }
        if (uriNode.isUri) {
            set.add(uriNode);
        }
        for (Map.Entry<Character, UriNode> entry : uriNode.nodes.entrySet()) {
            this.dfs(entry.getValue(), set);
        }
    }

    /**
     * 升级体验版:
     * 初始化时,遇到*位,当前*位node就汇集下面所有的资源放入当前node,
     * 匹配时,实际c字母映射没了,会走到*位,那么当前uri就遍历*位的叶子uri集合
     */
    /**
     * 注意: /user/*  /user/12 当前一颗星   直接匹配
     * /user/** /user/1  当前两颗星    当前位是* ? 直接匹配:false
     * <p>
     * /user/*  /user/   当前一颗星走不完 如果当前位是 / 且已经到头,
     * /user/*\/12  /user/ 当前位 / 到头,判断下一位count是否有*,且*位的isUri
     * <p>
     * /user/**\/list /user/qwe/list 不好判断的样子
     *
     * @param uri
     * @return
     */
    public String getBaseUri(String uri) {
        char[] arr = uri.toCharArray();
        UriNode cur = this.root;
        for (char c : arr) {

            UriNode node = cur.nodes.get(c);

            if (node == null) {
                //有带*的资源
                if ((node = cur.nodes.get('*')) != null) {
                    for (UriNode uriNode : node.childUriNodeSet) {
                        //开始比对 uri
                        if (this.antPathMatcher.matchStart(uriNode.value, uri)) {
                            return uriNode.value;
                        }
                    }
                }
                //没有当前资源
                return null;
            }

            //一直走下去
            cur = node;
        }

        //uri已经走完了
        if (cur.isUri) {
            return cur.value;
        }

        return null;
    }

}
